class Solution {//leetcode912——排序数组
private:
    vector<int> tmp;
private:
    void merge_sort(vector<int>& nums,int begin,int end){
        if(begin>=end) return;
        int mid=(end-begin)/2+begin;
        //分治
        merge_sort(nums,begin,mid);
        merge_sort(nums,mid+1,end);

        //归并——合并两个有序数组
        int cur1=begin,cur2=mid+1,i=begin;
        while(cur1<=mid&&cur2<=end){
            tmp[i++]=nums[cur1]<=nums[cur2]?nums[cur1++]:nums[cur2++];
        }
        while(cur1<=mid) tmp[i++]=nums[cur1++];
        while(cur2<=end) tmp[i++]=nums[cur2++];

        for(int i=begin;i<=end;i++) nums[i]=tmp[i];
    }
public:
    vector<int> sortArray(vector<int>& nums) {
        tmp.resize(nums.size());
        merge_sort(nums,0,nums.size()-1);
        return nums;
    }
};